package code;

import java.util.ArrayList;
import java.util.List;

public class Test1 {
	int m,n;
	//f1: 标记是否能到达太平洋， f2: 标记能否到达大西洋
    boolean f1,f2;
    //用于枚举四个方向
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    //check: 记录既能到达太平洋又能到大西洋的点，用于减少重复路径(剪枝)
    boolean[][] check;
    //判断某个位置是否被遍历过
    boolean[][] visit;
    List<List<Integer>> ret;
    List<Integer> path;
    public boolean dfs(int[][] heights,int i,int j){
    	//如果既能到太平洋又能到大西洋，或者某个节点的路径中的节点能到达，则直接返回
        if((f1==true&&f2==true)||(check[i][j]==true)) return true;

        for(int k=0;k<4;k++){
            int x=i+dx[k],y=j+dy[k];
            if(x>=0&&y>=0&&x<m&&y<n&&heights[i][j]>=heights[x][y]&&visit[i][j]==false){
                //更新f1,f2,注意，只要能到达就为true，而不是同时到达，因此无置false逻辑
            	f1=(x==0||y==0)?true:f1;
                f2=(x==m-1||y==n-1)?true:f2;
                visit[x][y]=true;
                if(dfs(heights,x,y)==true) 
                    return true;   
            }
        }
        return false;
    }
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        ret=new ArrayList<>();
        path=new ArrayList();
        m=heights.length;
        n=heights[0].length;
        check=new boolean[m][n];
        visit=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
            	//第一次要判断true，false
                f1=(i==0||j==0)?true:false;
                f2=(i==m-1||j==n-1)?true:false;
                //每次都要创建visit数组，为了在本次寻找路径中标记走过的位置
                //这里不能用全局的，因为显然判断节点能否到大西洋和太平洋是有重复路径的
                visit=new boolean[m][n];
                visit[i][j]=true;
                if(dfs(heights,i,j)==true){
                    path.clear();
                    path.add(i);
                    path.add(j);
                    check[i][j]=true;
                    ret.add(new ArrayList(path));
                }
            }
        }
        return ret;
    }
	
		
}
